package com.lc.lc312;

import java.util.*;


public class Main {

}

class Solution {
	public int[] nums;
	int[][] mp;
    public int maxCoins(int[] nums) {
    	
    	int n = nums.length;
    	int[] p = new int[n + 2];
    	p[0] = p[n + 1] = 1;
    	for (int i = 1; i <= n; i ++) {
    		p[i] = nums[i - 1];
    	}
    	this.nums = p;
    	this.mp = new int[n + 2][n + 2];
    	
    	for (int i = 0; i < n + 2; i ++) {
        	Arrays.fill(mp[i], -1);
    	}
    	
    	return solve(0, n + 1);
        
    }
    
    public int solve(int left, int right) {
    	if (mp[left][right] != -1) {
    		return mp[left][right];
    	}
    	int ans = 0;
		for (int i = left + 1; i < right; i ++) {
			int tmp = nums[left] * nums[i] * nums[right];
			ans = Math.max(ans, tmp + solve(left, i) + solve(i, right));

		}
		mp[left][right] = ans;
		return ans;
	}
}
